package com.sicheng.lc.周赛.分类.dp.数位;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/17 12:19
 */
public class 统计特殊整数 {
    //https://leetcode.cn/problems/count-special-integers/
    static int N = 10;

    static int[][] map = new int[N + 1][1 << 10];

    ArrayList<Integer> nums = new ArrayList<>(10);

    {
        for (int[] num : map) {
            Arrays.fill(num, -1);
        }
    }

    /**
     * @param i       正在填第i个位置
     * @param mask    前面的状态
     * @param limited 当前填的数字是否受限
     * @param isNum   前面是否是前导0
     */
    int dfs(int i, int mask, boolean limited, boolean isNum) {
        if (i == -1)
            return isNum ? 1 : 0;
        if (!limited && isNum && map[i][mask] != -1)
            return map[i][mask];

        int res = 0;
        if (!isNum)
            res += dfs(i - 1, 0, false, false);

        int r = limited ? nums.get(i) : 9;
        for (int j = isNum ? 0 : 1; j <= r; j++) {
            if ((mask >> j & 1) == 1)
                continue;

            res += dfs(i - 1, 1 << j | mask, limited && j == nums.get(i), true);
        }

        if (!limited && isNum)
            map[i][mask] = res;
        return res;

    }

    public int countSpecialNumbers(int n) {
        while (n != 0) {
            nums.add(n % 10);
            n /= 10;
        }
        return dfs(nums.size() - 1, 0, true, false);
    }
    public static void main(String[] args) {
        统计特殊整数 s = new 统计特殊整数();
        System.out.println(s.countSpecialNumbers(20));
    }
}
